Syllabus Information

5.1. Methodological overview

The learning process that is designed for this course is based on:

•      The presentation of the contents of the subject in lectures in the class-room
•      Solving problems in class.
•      Personal study of the subject by students.
•      The development of lab assignments by students, guided by teachers in the laboratory
•      Solving simple problems of increasing difficulty proposed by the teachers.
  

Keep in mind that the subject has both theoretical and practical orientation. Therefore, the learning process emphasizes both student attendance at lectures, as in the practical work in the laboratory, in solving simple problems of increasing difficulty, and individualized study.

5.2. Learning tasks

The program offered to the student to help him to achieve the expected results includes the following activities ...

• In classes taught in the classroom, the program of the course will be presented.
• In classes of case studies, problems will be solved using the concepts and techniques presented in the course syllabus.
• Practical work sessions will be held in a computer lab.

5.3. Syllabus

The course topics are organized around three pillars: (1) Theory of formal languages, with an emphasis on regular languages ​​and  context-free languages; (2) Fundamentals of Computability, to narrow what problems can be solved algorithmically; (3) Fundamentals of Algorithmic Complexity, to define what is efficiency of an algorithmic solution and the amount of resources an algorithm needs.

Topic 0: Preliminaries
Mathematical Preliminaries: sets, functions, relations, induction.
Definition of alphabet and language.

Topic 1: Regular Languages
Regular expressions and regular languages.
Deterministic finite automata (DFA) and nondeterministic finite automata (nDFA)
Equivalence between DFA and nDFA.
Properties of regular languages. Pumping Lemma

Topic 2: Context-Free Languages
Grammars and context-free languages.
Pushdown automata.
Simplification of grammars.
Properties of context-free languages. Pumping Lemma

Topic 3: Computability
Turing machines.
Languages ​​and Turing machines. Church-Turing thesis.
Decidability. Non-decidable problems.

Topic 4: Complexity
The classes of languages P and EXP.
The classes of languages NP and NP-complete.

The concepts, methods and tools of the above paragraphs are illustrated through examples, as realistic as possible, within the areas of: computer security, cryptography, natural language processing and compression of information.

5.4. Course planning and calendar

Scheduling of sessions and presentation of works

The schedule of the course will be defined by the School in the academic calendar of the corresponding academic year.

Student Work

The dedication of the student to achieve the learning outcomes in this course is estimated at 150 hours distributed as follows:

In the School of Engineering and Architecture of Zaragoza:

•     56 hours, approximately, of classroom activities (lectures, problems and laboratory)
•     40 hours of teamwork
•     51 hours of personal study (study booktexts and lecture notes, problem solving, preparing lessons and lab assignments)
•     3 hours deoted to the written final exam

At the Polytechnic University School of Teruel:

    60 hours of classroom activities (lectures, problems and laboratory)
    30 hours of teamwork
    55 hours of personal study (study booktexts and lecture notes, problem solving, preparing lessons and lab assignments)
    5 hours of evaluation activities